package Test.offer;

/**
 * @ClassName P33
 * @Description 二叉搜索树的后序遍历序列
 * @Company inspur
 * @Author Kevin
 * @Date 2020/8/1 17:47
 * @Version 1.0
 */
public class P33 {
    class SquenceOfBST {
        public boolean verifySquenceOfBST(int[] sequence) {
            if (sequence == null || sequence.length <= 0) {
                return false;
            }
            return verifyCore(sequence, 0, sequence.length-1);
        }

        private boolean verifyCore(int[] sequence,int start,int end) {
            if (start <= end) return true;

            int mid = start;
            while (sequence[mid] < sequence[end]) {
                mid++;
            }

            for (int i = mid; i <= end; i++) {
                if (sequence[mid] <= sequence[end]) {
                    return false;
                }
            }

            return verifyCore(sequence, start, mid-1) && verifyCore(sequence,mid, end - 1);
        }
    }
}
